Greedy

Wednesday, May 27, 2015

9:02 AM

<<greedy.pdf>>

Inserted from: <file://\\psf\Dropbox\Schoolworks\Waterloo Terms\4B\CS431\greedy.pdf>

Machine generated alternative text: CS 341: Algorithms
Douglas R. Stinson
David R Cheritor School of Computer Science
Univeraity of Waterloo
Winter. 2015
Miit,2015 1/110
O Course Information
O Introduction
O Divide-and-Conquer Algorithms
O Greedy Algorithms
W.tij,201S 2/110
O.k. Sd,a. (SS)

Machine generated alternative text: Table of Contents
O Greedy Algorithms
. Optimization Problems
. Design Strategy
. Interval Selection
. Interval Colouring
. Stable Marriage Problem
• Knapsack
. Coin Changing
WInter, 2015 24) / 11G
— Optlnmlzatlcn Probdenn
uptimizatlon i-’roblems
Problem: Given a problem instance, find a feasible solution that
maximizes (or minimizes) a certain objective function.
Problem Instance: Input for the specified problem.
Problem Constraints: Requirements that must be satisfied by any
feasible solution.
Feasible Solution: For any problem instance I, Feasib!e(I) is the set of all
outputs (i.e., solutions) for the instance I that satisfy the given
constraints.
Objective Function: A function f: FeasibÍe(I) —÷ Et u {O}. We often
think of f as being a profit or a cost function.
Optimal Solution: A feasible solution X E feasibÍe(I) such that the
profit f(X) is maximized (or the cost f(X) is minimized).
Dit. Stlinan (SES) WInter, 2015 01 / 110

Machine generated alternative text: I Dczlin Stratcr,
The Greedy Method
partial solutions
Given a problem instance I, it should be possible to write a
feasible solution X as a tuple [11,12.. .. x,] for some
integer ri, where r E X for all i. A tuple [xi,. . . ,x] where
i < n is a partial solution if no constraints are violated.
Note: it may be the case that a partial solution cannot be
extended to a feasible solution.
choice set
For a partial solution X = ra.. .. . xd where j < n, we
define the choice set
choice(X) = {y EX: [‘1..-. .x.y is a partial solution).
D.R. () Wtntar. 2015 fl/liD
“m D&,n Strateri
The Greedy Method (cont.)
local evaluation criterion
For any y e .1, g(y) is a local evaluation criterion that
measures the cost or profit of including y in a (partial)
solution.
extension
Given a partial solution X = [ri.... .Zj] where j < n,
choose y e choice(X) so that g(y) is as small (cx large) as
possible. Update X to be the (i± 1)-tuple [ri,... .Ii.y].
greedy algorithm
Starting with the “empty” partial solution, repeatedly extend
it until a feasible solution X is constructed. This feasible
solution may or may not be optimal.
WInw. 2015 03 ,‘ 110
D.R. SUman (SCS)

$Machine generated alternative text: 9rr_’mr C&n Chan.tng A Greedy Algorithm for Coin Changing Algorithm: Greedycbinchanging(D : array; T: integer) comment: D = [d1.. . . . d, rename the coins, by sorting if necessary, so that d1 > > dr. J\- t- O for i t- 1 to n 1t- LJ do 1y_ Y+a if T).O then return (fail) else return Gai,... _____ØcS) 4 CS 141 Wflte. 2015 110/110$

Created with Microsoft OneNote 2010
One place for all your notes and information